#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<deque>
#include<queue>
using namespace std;

//out of time
class Solution1{
    private:
    int val;
    vector<int> nums;

    public:
    Solution1(){
        val = 0;
    }

    void addNum(int num){
        nums.push_back(num);
        val++;
    }

    double findMedian(){
        vector<int> temp = nums;
        sort(temp.begin(), temp.end());
        double ret;
        if(val % 2 == 0){
            int index1 = val / 2 - 1, index2 = val / 2;
            ret = (double)(temp[index1] + temp[index2]) / 2;
        }else{
            int index = val / 2;
            ret = (double)temp[index];
        }
        return ret;
    }

};

class Solution2{
    private:
    priority_queue<int, vector<int>, less<int>> queMin;
    priority_queue<int, vector<int>, greater<int>> queMax;

    public:
    Solution2(){}

    void addNum(int num){
        if(queMin.empty() || num <= queMin.top()){
            queMin.push(num);
            if(queMax.size() + 1 < queMin.size()){
                queMax.push(queMin.top());
                queMin.pop();
            }
        }else{
            queMax.push(num);
            if(queMax.size() > queMin.size()){
                queMin.push(queMax.top());
                queMax.pop();
            }
        }
    }

    double findMedian(){
        if(queMin.size() > queMax.size()){
            return queMin.top();
        }else{
            return (queMin.top() + queMax.top()) / 2.0;
        }
    }

};

void test1(){
    Solution1* s = new Solution1();

    s->addNum(1);
    s->addNum(2);
    cout << s->findMedian() << endl;
    s->addNum(3);
    cout << s->findMedian() << endl;
}

void test2(){
    Solution2* s = new Solution2();

    s->addNum(1);
    s->addNum(2);
    cout << s->findMedian() << endl;
    s->addNum(3);
    cout << s->findMedian() << endl;
}

int main(void){
    test2();

    return 0;
}